package com.offer;


import com.utils.DataUtils;

import java.util.ArrayList;
import java.util.Arrays;

public class Test38 {

    public String[] permutation(String s) {
        ArrayList<String> result = new ArrayList<>();

        char[] chars = s.toCharArray();
        Arrays.sort(chars);

        StringBuilder stringBuilder = new StringBuilder();

        boolean[] visited = new boolean[s.length()];

        dfs(chars, stringBuilder, visited, result);

        return result.toArray(new String[0]);
    }

    private void dfs(char[] chars, StringBuilder stringBuilder, boolean[] visited, ArrayList<String> result) {
        if (stringBuilder.length() == chars.length) {
            result.add(stringBuilder.toString());
            return;
        }


        for (int i = 0; i < chars.length; i++) {

            if (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1]) {
                continue;
            }

            if (visited[i]) {
                continue;
            }

            visited[i] = true;

            stringBuilder.append(chars[i]);

            dfs(chars, stringBuilder, visited, result);

            stringBuilder.deleteCharAt(stringBuilder.length() - 1);

            visited[i] = false;
        }
    }

    public static void main(String[] args) {


        Test38 test34 = new Test38();
        String[] result = test34.permutation("aaab");
        DataUtils.printArrayString(result);
    }

}
